/*
 *
 *  File: 'trie.h'
 *
 *  Author: Samip Shah <samipshah@alumni.cmu.edu>
 *  Date: Sep 19, 2011
 *
 */

#ifndef TRIE_H
#define TRIE_H

#define DATA(x) (x)->value
#define NEXT_V(x) (x)->nextArray
#define PUSH_V(x, y) (x)->push_back((y))
#define SIZE_V(x) (x)->size()
#define ELEMENT(x,y) (*(x))[(y)]
#include <vector>
#include <tr1/functional>
#include <functional>
#include <iostream>

template<typename T>
class Trie {
	struct Node {
		T value;
		std::vector<Node*> nextArray;
    Node(T val):value(val){}
    ~Node() {
      int size = nextArray.size();
      for(int i=0; i < size; i++) {
        delete nextArray[i];
      }
    }
	};

  std::vector<Node*> TOP;

  T sentinel;
  int TOTAL_SIZE;

  public:
  enum FUNC {
    PRINT,
    SIZE
  };
  typedef std::tr1::function<void (Node*)> visit_func;
  Trie(){}
  Trie(T sent):sentinel(sent){}
  ~Trie() {
    int size = TOP.size();
    for(int i=0; i < size; i++) {
      delete TOP[i];
    }
  }
  void setSentinel(T a_sentinel) {
    sentinel = a_sentinel;
  } 
  
  bool add(const T array[], int len);
  bool exists(const T array[], int len);
  void preOrderTraversal(FUNC a);
  void preOrderTraversal_r(Node* top, visit_func f);
  void print(Node* node);
  void size(Node* node);
  unsigned int total_size() { 
    preOrderTraversal(SIZE);
    return TOTAL_SIZE;
  }
};

template<typename T>
void Trie<T>::preOrderTraversal(FUNC a) {
  visit_func f;
  switch(a) {
    case PRINT: 
      { 
        f = std::tr1::bind(\
            std::tr1::mem_fn(&Trie<T>::print), this,\
            std::tr1::placeholders::_1);
      } break;
    case SIZE:
      {
        TOTAL_SIZE = 0;
        f = std::tr1::bind(\
            std::tr1::mem_fn(&Trie<T>::size), this,\
            std::tr1::placeholders::_1);
      }
  }

  int size = TOP.size();
  
  for(int i = 0; i < size ; i++ ) {
    preOrderTraversal_r(TOP[i], f);
  }
}

template<typename T>
void Trie<T>::size(Node* node) {
  TOTAL_SIZE += sizeof(Node);
}

template<typename T>
void Trie<T>::print(Node* node) {
  if(DATA(node) == sentinel)
    std::cout << std::endl;

  std::cout << DATA(node) << ",";
}

template<typename T>
void Trie<T>::preOrderTraversal_r(Node* top, visit_func f) {
  if(!top) return;
  //visit func
  f(top);

  int size = (NEXT_V(top)).size();
  for(int i=0 ; i < size ; i++) {
    preOrderTraversal_r(NEXT_V(top)[i], f);
  }
}

/*
 * array must be sentinel terminated
 */
template<typename T>
bool Trie<T>::add(const T array[], int len) {

  std::vector<Node*>* ITER = & TOP;

  for(int j=0; j <= len; j++) {
    bool found = false;
    int size = SIZE_V(ITER);
    int i = 0;
    for(; i < size; i++) {
      if(DATA(ELEMENT(ITER, i)) == array[j]) {
        found = true;
        break;
      }
    }

    if(found) {
      ITER = & NEXT_V(ELEMENT(ITER, i));
    } else {
      Node* temp = new Node(array[j]);
      PUSH_V(ITER, temp);
      int size = SIZE_V(ITER);
      ITER = & NEXT_V(ELEMENT(ITER, (size-1)));
    }
  }

  return true;
}

/*
 * array must be sentinel terminated
 *
 */
template<typename T>
bool Trie<T>::exists(const T array[], int len) {
  std::vector<Node*>* ITER = & TOP;

  for(int j=0; j <= len; j++) {
    bool found = false;
    int size = SIZE_V(ITER);
    int i=0;
    for(; i < size; i++) {
      if(DATA(ELEMENT(ITER, i)) == array[j]) {
        found = true;
        break;
      }
    }

    if(found) {
      ITER = & NEXT_V(ELEMENT(ITER, i));
    } else {
      return false;
    }
  }

  return true;
}

#undef DATA
#undef NEXT_V
#undef PUSH_V
#undef SIZE_V
#undef ELEMENT

#endif
